package LearnDataStructure.a_线性结构.例题;

import java.util.HashSet;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-02 21:18
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.a_线性结构.例题
 */
public class a_未排序双向链表去重byHashSet {
    public static void main(String[] args) {
        a_未排序双向链表去重byHashSet test = new a_未排序双向链表去重byHashSet();
        int[] arr = new int[]{9, 8, 7, 6, 6, 4, 2, 11, 11, 3, 4};
        test.useRemoveE(arr);
    }

    /**
     * 带缓冲区的版本
     * 这是用空间换时间；
     * @param arr
     */
    public void useRemoveE(int[] arr) {
        CaseNode head = new CaseNode();
        CaseNode tail = new CaseNode();
        head.next = tail;
        tail.pre = head;
        CaseNode p = head;
        for (int i = 0; i < arr.length; i++) {
            CaseNode newNode = new CaseNode(arr[i]);
            p.next = newNode;
            newNode.pre = p;
            newNode.next = tail;
            tail.pre = newNode;
            p = p.next;
        }
        removeE(head, tail);
        CaseNode temp = head.next;
        while (temp != tail) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }

    public void removeE(CaseNode head, CaseNode tail) {
        HashSet set = new HashSet();
        CaseNode p = head.next;
        while (p != tail) {
            CaseNode temp = p.next;
            if (set.contains(p.data)) {
                p.pre.next = p.next;
                p.next.pre = p.pre;
                p.pre = null;
                p.next = null;
            } else {
                set.add(p.data);
            }
            p = temp;
        }
    }
}
